package LC239;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

/*滑动窗口最大值，大小为k的滑动窗口在一个整数数组中滑动，每次向右移动一位，请返回滑动窗口的最大值*/

public class LC239 {
    public static void main(String[] args) {
        LC239 lc239 = new LC239();
        int nums[]={1,3,-1,-3,5,3,6,7};
        int k=3;
        int[] res=lc239.solution(nums,k);
        System.out.println(Arrays.toString(res));

    }

    public int[] solution(int nums[],int k)
    {
        int[] result=new int[nums.length-k+1];
        //算法核心：deque中元素是从大到小的顺序存储滑动窗口的元素索引
        Deque<Integer> deque=new LinkedList<>();
        for(int i=0;i<nums.length;i++)
        {
            //移除队列中不在滑动窗口范围内的元素
            if(!deque.isEmpty() && deque.peekFirst()<i-k+1){
                deque.pollFirst();
            }
            //当新的数大于deque中的最后一个元素时，则移除队列中最后的元素
            while(!deque.isEmpty() && nums[deque.peekLast()]<nums[i]){
                deque.pollLast();
            }
            //从队列的后面插入当前的数
            deque.offerLast(i);
            //当遍历到第k个元素时，开始记录窗口最大值
            if(i>=k-1)
            {
                result[i-k+1]=nums[deque.peekFirst()];
            }
        }
        return result;

    }

}
